With the ever increasing presence of computing devices, and positioning devices, such as global positioning systems (GPSs), as well as electronic information regarding streets, routes, schedules, traffic conditions, and the like, determining an efficient route from one point to another is becoming an important area of focus. Indeed, given a map, such as map 100 on FIG. 1, with a variety of routes between origin Point A 102 and destination Point B 104, many drivers would like to know which is the “best” route to take. Of course, the “best” route may involve a variety of factors, such as shortest distance, least amount of travel time, least congested route, most scenic route, and the like. However, if what it means to select the “best” could be specified, it would be important and useful to be able to determine such routes.
As those skilled in the art will appreciate, a basic algorithm, called Dijkstra's Algorithm, formulated by Edsger W. Dijkstra, serves, at least in part, as a foundation for nearly all vehicle routing algorithms. An explanation of Dijkstra's Algorithm, sometimes referred to as a double bucket algorithm, may be found at the following Internet location: http://www.kvocentral.com/kvopapers/pollitt.pdf. In order to determine the best solution between two points, the routes are identified according to nodes and edges. For example, with reference to FIG. 2 which illustrates the exemplary map 100 of FIG. 1, exemplary nodes would include 202, 204, and 206. Edges are segments between two nodes, such as edge 208, 210, and 212. Each edge is associated with a cost, based on some evaluation or determination. For example, assuming the cost is to be determined in the amount of time it takes to traverse the route, each edge (a segment of a route between two nodes) is associated with its cost, i.e., the amount of time it takes to traverse that segment. As shown in FIG. 2, the map 100 further illustrates the cost of each edge, as indicated by the numbers within the map 100. Simply stated, Dijkstra's Algorithm sums up the costs of all edges on every route, and selects the route that resulted in the lowest cost that reaches the destination.
While Dijkstra's Algorithm will find the shortest route between two points according to the costs associated with each edge, one of the problems of the algorithm is that it finds all solutions between two points. In fact, it tends to find all solutions between an origin and any other location. FIG. 3 is a pictorial diagram illustrating how a basic implementation of Dijkstra's Algorithm between Point A 102 and Point B 104 begins at Point A and extends out in each direction, as indicated by the concentric rings. As FIG. 3 suggests, Dijkstra's algorithm even evaluates solutions that do not ultimately reach Point B 104, and even go in an opposite direction from Point B. Clearly, such comprehensive examination of all routes is very inefficient, and would be on devices of limited processing capability.
As Dijkstra's Algorithm is so inefficient, most routing systems have adapted a modified form of Dijkstra's algorithm referred to as the A* (pronounced A Star) Algorithm. In short, an A* Algorithm makes a “guess” as to which edges should be examined first, and which should be delayed, if examined at all. Depending on the quality of the “guess,” the A* Algorithm can greatly improve the efficiency of route determination. FIG. 4 is a pictorial diagram illustrating the exemplary map 100, and further illustrating how a typical A* Algorithm expands from an origin, such as Point A 102, to a destination, in this case Point B 104. Those edges and nodes within the ellipse 106, represent those that would likely be examined during the A* best route selection processes, and the internal lines indicate how the route selection expands from Point A 102 to Point B 104.
Those skilled in the art will appreciate that there are numerous algorithms for “guessing” in an A* Algorithmic selection, and an implementor is free to choose any one. For example, in an actual implementation, the “guess” is made according to a distance from a vector 510 extending through an origin, such as Point A 102, and a destination, such as Point B 10, as well as the distance of a node from the vector. For example, FIG. 5 is a pictorial diagram illustrating the exemplary map 100 of FIG. 1, and for illustrating the computation of the guess to determine if an edge should be evaluated during an A* Algorithmic selection. In particular, assuming that the “guessing” algorithm has traversed to both nodes 504 and 506, and then determines which route to further explore, an evaluation according to the predetermined guessing algorithm is made. In this case, the distance between node 504 and where it intersects 502 in a perpendicular manner with the vector 510 is added to the distance between the intersection 502 and the destination, Point B 104. The distance between node 506 and its intersection 508, is added to the distance from intersection 508 to the destination, Point B 104. These values are then used to weight the costs from nodes 504 and 508. These weighted costs are then used by the base double bucket algorithm, as set forth in Dijkstra's algorithm, to determine which route to pursue.
One of the advantages of the “guess” described above, i.e., based on the vector running through the origin to the destination, is that when the route data is sectioned into grids, such as will be described below in regard to the present invention, the selection algorithm tends to favor those routes that lie along the vector, generally narrowing the width of the overall route selection/evaluation. This also tends to minimize the number of grids that the selection algorithm must load during the route selection.
As indicated above, another issue associated with Dijkstra's Algorithm is that many devices upon which route selection is performed is of limited processing abilities. It is simply impracticable for many of the devices to evaluate all routes, then select the best. Even still, many of these devices cannot hold all information (particularly route information) between an origin and destination, at least in memory.
In light of the information above, what is needed are routing devices that implement efficient routing algorithms as well as make efficient use of the routing information in memory. The present invention addresses these and other issues associated with routing/navigation.